package 数据结构和算法.剑指offer.链表.从尾到头打印链表;

import 工具.打印.PrintUtil;

import java.util.Arrays;
import java.util.Stack;

/**
 * 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * <p>
 * 正常来说链表的遍历是从前向后，而题目要求的是从后向前。
 * 我们首先可以想到的方法就是经指针从给定链表的头结点向后遍历到最后一个结点，
 * 然后依次取出放入数组即可。事实上，这里我们应用栈的“先进后出”的特性，
 * 就可以实现算法。首先从头向尾把数据依次压入栈，再依次出栈到新的数组中，就是我们要的结果。
 */
public class Test {
    public static void main(String[] args) {
        ListNode head = new ListNode(null, 1);
        ListNode two = new ListNode(null, 2);
        ListNode three = new ListNode(null, 3);
        head.setNext(two);
        two.setNext(three);

        PrintUtil.println(Arrays.toString(reversePrint(head)));
    }

    public static int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }

        int size = stack.size();
        int[] arry = new int[size];
        for (int i = 0; i < size; ++i) {
            arry[i] = stack.pop().value;
        }

        return arry;
    }

    static class ListNode {
        private ListNode next;
        private int value;

        public ListNode(ListNode next, int value) {
            this.next = next;
            this.value = value;
        }

        public ListNode getNext() {
            return next;
        }

        public void setNext(ListNode next) {
            this.next = next;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
    }
}
